package Alg;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class Dijkstra<V, E> {
	
	private final Function<V, Map<E, V>> getNeighbors;
	private final Function<E, Integer> getDistance;
	
	private final Function<V, Vertex> getVertex = new Function<V, Vertex>() {

		private final Map<V, Vertex> vertices = new HashMap<V, Vertex>();
		
		@Override
		public Vertex apply(V v) {
			if (!vertices.containsKey(v)) {
				vertices.put(v, new Vertex(v));
			}
			return vertices.get(v);
		}
	};

	public Dijkstra(Function<V, Map<E, V>> getNeighbors, Function<E, Integer> getDistance) {
		this.getNeighbors = getNeighbors;
		this.getDistance = getDistance;
	}
	
	public List<E> shortestPath(V start, V end) {
		
		// startknoten in menge vertices einfuegen
		Set<Vertex> vertices = new HashSet<Vertex>();
		Vertex startV = getVertex.apply(start);
		Vertex endV = getVertex.apply(end);
		startV.distance = 0;
		vertices.add(startV);
		
		while (!vertices.isEmpty()) {
			
			Vertex next = getNext(vertices);
			next.visited = true;
			vertices.remove(next);
			
			// vorabbruch
			if (endV.distance < next.distance) break;
			
			Map<E, V> neighbors = getNeighbors.apply(next.v);
			for (Entry<E, V> entry : neighbors.entrySet()) {
				
				Vertex next1 = getVertex.apply(entry.getValue());
				if (!next1.visited) {
					final E edge = entry.getKey();
					int distance = next.distance + getDistance.apply(edge);
					if (distance < next1.distance) {
						next1.distance = distance;
						next1.preVertex = next;
						next1.edge = edge;
					}
					vertices.add(next1);
				}
			}
		}
		
		return createPath(endV);
	}
	
	private Vertex getNext(Set<Vertex> set) {
		
		Iterator<Vertex> it = set.iterator();
		Vertex next = it.next();
		while (it.hasNext()) {
			Vertex isNext = it.next();
			if (isNext.distance < next.distance) {
				next = isNext;
			}
		}
		
		return next;
	}
	
	private List<E> createPath(Vertex end) {
		
		List<E> path = new ArrayList<E>();
		Vertex next = end;
		while (next.edge != null) {
			path.add(next.edge);
			next = next.preVertex;
		}
		
		Collections.reverse(path);
		
		return path;
	}

	public interface Function<I, O> {
		O apply(I input);
	}
	
	private class Vertex {
		
		boolean visited = false;
		int distance = Integer.MAX_VALUE;
		
		Vertex preVertex = null;
		E edge = null;
		
		final V v;
		
		public Vertex(V v) {
			this.v = v;
		}
	}
}
